package genetica.cruce;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Random;
import java.util.TreeMap;

import genetica.cromosomas.genes.*;

/**
 * Implementa una tabla de conectividad para un grafo.
 * 
 */
public class TablaConectividad {

	private TreeMap<Gen, ArrayList<Gen>> _tabla;
	private int tam = 0;
	public TablaConectividad() {

	}

	public TablaConectividad(Gen[] padre, Gen[] madre) {

		_tabla = new TreeMap<Gen, ArrayList<Gen>>();
		this.tam = padre.length;
		for (int i = 0; i < tam; i++) {
			int posAnt = ((i - 1) + tam) % tam;
			int posPost = (i + 1) % tam;

			Gen g1 = padre[i];
			Gen g1Ant = padre[posAnt];
			Gen g1Post = padre[posPost];

			ArrayList<Gen> list = new ArrayList<Gen>();
			list.add(g1Ant);
			list.add(g1Post);
			_tabla.put(g1, list);
		}
		for (int i = 0; i < tam; i++) {
			int posAnt = ((i - 1) + tam) % tam;
			int posPost = (i + 1) % tam;
			Gen g2 = madre[i];
			Gen g2Ant = madre[posAnt];
			Gen g2Post = madre[posPost];
			ArrayList<Gen> list = _tabla.get(g2);
			if (!visitada(list, g2Ant))
				list.add(g2Ant);
			if (!visitada(list, g2Post))
				list.add(g2Post);
		}
	}

	public ArrayList<Gen> dameRuta() {
		Gen ultima = _tabla.firstKey();
		return dameRuta(new ArrayList<Gen>(), ultima);
	}

	private ArrayList<Gen> dameRuta(ArrayList<Gen> ciudadesVisitadas, Gen ultima) {
		Random r = new Random();
		ArrayList<Gen> proximas = (ArrayList<Gen>) _tabla.get(ultima).clone();
		Gen proxima  = null;
		while (proximas.size() != 0) {
			proxima = proximas.remove(r.nextInt(proximas.size()));
			if (!(visitada(ciudadesVisitadas, proxima))) {
				ciudadesVisitadas.add(proxima);
				// ya las tengo todas??
				if (ciudadesVisitadas.size() == this.tam)
					return ciudadesVisitadas;
				ArrayList<Gen> ruta = dameRuta(ciudadesVisitadas, proxima);
				if (ruta != null) {
					return ruta;
				}
				ciudadesVisitadas.remove(proxima);

			}
		}
		return null;
	}

	private static boolean visitada(ArrayList<Gen> lista, Gen gen) {
		for (int i = 0; i < lista.size(); i++) {
			if (lista.get(i).equals(gen))
				return true;
		}
		return false;
	}

}